// 环形链表 II
public class DetectCycle {

  /**
   * 快慢指针法：
   * 定义两个指针，快指针走两个节点，慢指针走一个节点，如果是环形链表的话，两个指针能相遇
   * 时间复杂度：O(N)
   * 空间复杂度：O(1)
   */
  public ListNode detectCycle(ListNode head) {
    ListNode fastIndex = head;
    ListNode slowIndex = head;
    while (fastIndex != null && fastIndex.next != null) {
      fastIndex = fastIndex.next.next;
      slowIndex = slowIndex.next;
      if (fastIndex == slowIndex) {// 有环
        ListNode index1 = fastIndex;
        ListNode index2 = head;
        while (index1 != index2) {
          index1 = index1.next;
          index2 = index2.next;
        }
        return index1;
      }
    }
    return null;
  }

  // 定义一个指针的节点
  public static class ListNode {
    // 节点的值
    int val;
    // 下一个节点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {

    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
      this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}